package com.demo.java.OD201_250.OD215;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【寻找链表的中间结点】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145914363
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建Scanner对象读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取链表的起始节点地址和节点数
        int head = scanner.nextInt();
        int n = scanner.nextInt();

        // 使用HashMap来存储链表信息
        Map<Integer, int[]> link = new HashMap<>();

        // 读取每个节点的信息
        while (n-- > 0) {
            // 读取每个节点的地址、数据和next地址
            link.put(scanner.nextInt(), new int[]{scanner.nextInt(), scanner.nextInt()});
        }

        // 计算并输出最大差异的结果
        System.out.println(solveMethod(head, link));
    }

    private static int solveMethod(int head, Map<Integer, int[]> link) {
        int slow = head, fast = head;

        // 快慢指针遍历链表
        while (fast != -1 && link.get(fast)[1] != -1) {
            slow = link.get(slow)[1];
            fast = link.get(link.get(fast)[1])[1];
        }

        // 返回slow指针所在位置的值（最大差异的计算结果）
        return link.get(slow)[0];
    }
}